While the regulation of protection of personal information and confidential information is strengthened, a market of services that use such information is expanding. Further, a concealing technique is used in which data can be utilized while personal information and confidential information are maintained in a protected state. Among the concealing techniques, there is a technique that uses an encryption technique and a statistical technique according to a data type and service requirements.
As a concealing technique that uses an encryption technique, a homomorphic encryption technique is known. The homomorphic encryption technique is one of public key cryptosystems that use a pair of different keys for encryption and decryption and is an encryption technique that can handle encrypted data as it is. For example, when an encryption function of a homomorphic encryption method related to addition or multiplication for plain texts m1 and m2 is E, characteristics of the following formula (1) or (2) are established.E(m1)+E(m2)=E(m1+m2)  (1)E(m1)*E(m2)=E(m1*m2)  (2)
The characteristics where the formula (1) is established are referred to as homomorphism for addition and the characteristics where the formula (2) is established are referred to as homomorphism for multiplication.
When the homomorphic encryption method is used, it is possible to obtain an encrypted text of an addition or multiplication calculation result without decrypting the encrypted text by addition or multiplication of the encrypted text. The characteristics of the homomorphic encryption are used in a field of electronic voting and electronic cash and a field of cloud computing. As the homomorphic encryption method, an RSA (Rivest Shamir Adleman) encryption method used for multiplication and an Additive ElGamal encryption method used for addition are typical.
In recent years, a homomorphic encryption method that can be used for both addition and multiplication is known, and further, a homomorphic encryption method which can be used for both addition and multiplication and whose processing performance and encrypted data size are practical is known.
Here, as an example, the homomorphic encryption method will be described. First, mainly three key generation parameters (n, q, t) are prepared for generating an encryption key. Here, n is a power of two and called a lattice dimension, q is a prime number, and t is an integer smaller than q. In a procedure for generating an encryption key, first, as a secret key, an n-dimensional polynomial equation sk in which each coefficient is very small is randomly generated. The smallness of each coefficient is limited by a certain parameter o. Next, an n-dimensional polynomial equation a1 in which each coefficient is smaller than q and an n-dimensional polynomial equation e in which each coefficient is very small are randomly generated.
Then, “a0=−(a1*sk+t*e)” is calculated and a pair (a0, a1) is defined as a public key pk. However, when the polynomial equation of a0 is calculated, a (less than n)-dimensional polynomial equation is calculated at all times by calculating as xn=−1, xn+1=−x, and so on for an (n or more)-dimensional polynomial equation. Further, as a coefficient of the polynomial equation, a remainder obtained by dividing the coefficient by the prime number q is outputted. A space in which such a calculation is performed is often academically represented as Rq:=Fq[x]/(xn+1).
Next, three n-dimensional polynomial equations u, f, and g in which each coefficient is very small are randomly generated for a plain text data m represented by an n-dimensional polynomial equation in which each coefficient is smaller than t and a public key pk=(a0, a1), and encrypted data E(m, pk)=(c0, c1) of the plain text data m is defined as follows. That is to say, (c0, c1) is calculated as c0=a0*u+t*g+m, and c1=a1*u+t*f. These calculations are also performed in the space Rq.
Then, for two encrypted texts E(m1, pk)=(c0, c1) and E(m2, pk)=(d0, d1), encryption addition E(m1, pk)+E(m2, pk) is calculated as (c0+d0, c1+d1) and encryption multiplication E(m1, pk)*E(m2, pk) is calculated as (c0+d0, c0*d1+c1*d0, c1*d1). When the encryption multiplication is performed in this way, note that the data size of the encrypted text becomes three-component vector from two component vector.
Finally, regarding a decryption process, for an encrypted text c=(c0, c1, c2, and so on) (here, it is assumed that the number of components of encrypted text data is increased by an encryption operation such as a plurality of encryption multiplications), decryption is performed by calculating as Dec(c, sk)=[c0+c1*sk+c2*sk2+ . . . ]q mod t by using the secret key sk. Here, regarding the value of [z]q, a remainder w is calculated by dividing an integer z by q, and if w<q, [z]q=w is outputted, and if w≧q, [z]q=w−q is outputted. Further, a mod t means a remainder obtained by dividing an integer a by t.
Hereinafter, numerical examples will be illustrated.The secret key sk=Mod(Mod(4,1033)*x3+Mod(4,1033)*x2+Mod(1,1033)*x,x2+1)The public key pk=(a0,a1)a0=Mod(Mod(885,1033)*x3+Mod(519,1033)*x2+Mod(621,1033)*x+Mod(327,1033),x4+1)a1=Mod(Mod(661,1033)*x3+Mod(625,1033)*x2+Mod(861,1033)*x+Mod(311,1033),x4+1)E(m,pk)=(c0,c1)The plain text data m=3+2x+2x2+2x3 c0=Mod(Mod(822,1033)*x3+Mod(1016,1033)*x2+Mod(292,1033)*x+Mod(243,1033),x4+1)c1=Mod(Mod(840,1033)*x3+Mod(275,1033)*x2+Mod(628,1033)*x+Mod(911,1033),x4+1)
In the values described above, the key generation parameter (n, q, t) is set to (4, 1033, 20). Further, Mod(a, q) means a remainder obtained by dividing the integer a by the prime number q, and Mod(f(x), x4+1) means a remainder polynomial equation obtained by dividing a polynomial equation f(x) by a polynomial equation x4+1. However, it means that x4=−1, x5=x, . . . and the like.
When the homomorphic encryption method described above is used for a concealment calculation, each user who provides data encrypts data by using a common public key generated by an analyst who analyzes the data and stores the encrypted data in an analysis device. The analysis device analyzes the encrypted data as it is. The analyst obtains an analysis result by decrypting the data analyzed by the analysis device by using his or her secret key.
Cloud computing has become widely used, so that a plurality of analysts may share and use the encrypted data in the concealment calculation. Therefore, a concealment calculation using re-encryption in which the encryption key is replaced is widely used.
For example, each user who provides data stores encrypted data encrypted with his or her public key in the analysis device. The analysis device replaces a key of the encrypted data with a key of the analyst by using a secret key of each user encrypted with a public key of the analyst, that is to say, the analysis device performs the re-encryption. The analysis device analyzes the encrypted data, which is re-encrypted with the key of the analyst, as it is. The analyst obtains an analysis result by decrypting the data analyzed by the analysis device by using his or her secret key.
Patent Literature 1: Japanese Laid-open Patent Publication No. 2008-176193
Patent Literature 2: Japanese Laid-open Patent Publication No. 2012-220834
Patent Literature 3: Japanese Laid-open Patent Publication No. 2012-237881
Non Patent Literature 1: C. Gentry, “Fully Homomorphic encryption using ideal lattices”, STOC 2009, ACM, pp. 169-178, 2009.
Non Patent Literature 2: K. Lauter, M. Naehrig and V. Vaikuntanathan, “Can Homomorphic Encryption be Practical?”, In ACM workshop on Cloud Computing Security Workshop—CCSW 2011, ACM, pp. 113-124, 2011.
However, a re-encryption process in the homomorphic encryption method described above takes time because the re-encryption process includes many complicated encryption processes and decryption processes. For example, in an analysis device installed on a cloud system or the like, data encrypted with a different encryption key is analyzed as it is, and then the data is further encrypted with an encryption key of an analyst. Therefore, each process for the data is performed in a state in which the data is encrypted, so that the processing cost is high.